package com.lwt.codetop.twoPointers;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//15. 三数之和
/**
 * 找到三个数和为0的所有不重复的方案：
 *  暴力思路：排序 + 去重 + 三重暴力循环 时间复杂度：O（n^3)
 *  排序 + 双指针优化：枚举a，双指针枚举b, c，时间复杂度：O（n^2), 注意去重即可
 *  排序是为了更好的去重
 */
public class ThreeSum {


    public static void main(String[] args) {
        // 构建测试用例
        int[] nums = {-1,0,1,2,-1,-4};
        // 1. 排序
        Arrays.sort(nums);
        // 2. 三数之和
        List<List<Integer>> res =  threeSum(nums);
        System.out.println(res);
    }

    /**
     * 三数之和
     * @param nums
     * @return
     */
    private static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        int n = nums.length;
        for(int i = 0; i < n; i ++){// 枚举a
            // 对a去重 注意这里是if
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            // 双指针枚举b,c，找到方案并去重
            int l = i + 1, r = n - 1;
            while(l < r){
                // 三数之和 ---》 且我们之前排序了 有序性
                int s = nums[i] + nums[l] + nums[r];
                if(s > 0) {
                    r -= 1;
                }
                else if (s < 0){
                    l += 1;
                }
                else{ // 找到答案
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    //对b c进行去重
                    while (l < r && nums[l] == nums[l + 1]) l += 1;
                    while (l < r && nums[r] == nums[r - 1]) r -= 1;
                    // 指针移动，为一下次准备
                    l += 1;
                    r -= 1;
                }
            }
        }
        return res;
    }
}
